\documentclass[a4paper]{article}

\usepackage[utf8x]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amsmath, amssymb}
\usepackage[french]{babel}
\usepackage{fullpage}
\usepackage{listings}
\usepackage{color}

\usepackage{url}
\urlstyle{sf}

\selectlanguage{french}
\lstset{ %
	%language=C,                % choose the language of the code
	basicstyle=\footnotesize,       % the size of the fonts that are used for the code
	numbers=left,                   % where to put the line-numbers
	numberstyle=\footnotesize,      % the size of the fonts that are used for the line-numbers
	stepnumber=1,                   % the step between two line-numbers. If it's 1 each line will be numbered
	numbersep=5pt,                  % how far the line-numbers are from the code
	backgroundcolor=\color{white},  % choose the background color. You must add \usepackage{color}
	showspaces=false,               % show spaces adding particular underscores
	showstringspaces=false,         % underline spaces within strings
	showtabs=false,                 % show tabs within strings adding particular underscores
	%frame=single,                   % adds a frame around the code
	tabsize=2,                      % sets default tabsize to 2 spaces
	captionpos=b,                   % sets the caption-position to bottom
	breaklines=true,                % sets automatic line breaking
	breakatwhitespace=false,        % sets if automatic breaks should only happen at whitespace
	escapeinside={\%*}{*)}          % if you want to add a comment within your code
}
\title{Interpolation rapide des polynômes en une variable à coefficients dans $\mathbb{Q}$}
\author{Philippe BERTHELIN\\
	Karim MIRI\\
	Guillaume PIERRON\\
	Université Pierre et Marie Curie - Paris VI}
\date{Mai 2008}
\begin{document}
	\maketitle
	\section{Détails des codes sources}
Voici l'ensemble des fichiers que nous avons écrits, tous en langage Maple, en suivant les algorithmes donnés dans l'énoncé :
\begin{itemize}
	\item \textit{euclide.mpl} $\rightarrow$ contient l'algorithme de division Euclidienne
	\item \textit{interpolation.mpl} $\rightarrow$ contient l'interpolation de Lagrange
	\item \textit{init\_arbre.mpl} $\rightarrow$ permet de construire l'arbre des sous-produits d'un polynôme
	\item \textit{fasteval.mpl} $\rightarrow$ effectue l'évaluation rapide de polynômes
	\item \textit{fracsum.mpl} $\rightarrow$ effectue la somme de fractions
	\item \textit{fast\_interpoly.mpl} $\rightarrow$ effectue la totalité de l'interpolation rapide
	\item \textit{modules.mpl} $\rightarrow$ permet de lire tous ces fichiers d'un coup dans maple
\end{itemize}
	
	\section{Résultats expérimentaux}
Lors de nos test, nous avons pu constater que notre implantation fournissait des résultats corrects, mais de manière peu performante. Nous pensons que la quantité de mémoire nécessaire à nos calculs est supérieure à celle nécessaire à l'interpolation de Lagrange, la mémoire \og swappe \fg, ce qui nous donne de plus mauvaises performances.
\\
Voici l'exemple d'un test de notre implantation:
\lstinputlisting{results.log}


Ceci montre, comme nous l'avons dit plus haut, que notre interpolation rapide consomme plus de mémoire que notre interpolation de Lagrange, et qu'elle s'avère plus lente (ici sur des listes de 128 entiers aléatoires).
S'il ne s'agit effectivement pas d'un problème de mémoire, nous n'en connaissons pas la cause.
	
	\section{Théorie}
	\subsection{Analyse de complexité}
Au préalable il faut determiner le gain apporté par les algorithmes de type \og diviser pour régner \fg.
Il existe un théorème indiquant la complexité de tels algorithmes dans le cas de sous-problèmes de même taille\footnote{source : \url{http://fr.wikipedia.org/}, article "Diviser\_pour\_régner\_(informatique)"} (ce qui est notre cas) :
$$ \text{Si } C(n) = aC(n / b) + cn \text{, avec } c(1) = \text{constante, alors:}$$
\begin{itemize}
	\item si $a < b, C(n) = O(n)$
	\item si $a = b, C(n) = O(n \log{(n)})$
	\item si $a > b, C(n) = O(n^{log_b(a)})$
\end{itemize}
\newpage
On analyse la complexité comme suit :
\begin{enumerate}
	\item \textbf{Arbre des sous-produits :} \\
	Le coût de la construction vaut deux fois le coût de la construction des fils, plus un coût dû à la multiplication des facteurs, en appliquant le théorème de stratégie \og diviser pour régner \fg, ici $a = b = 2$, on aura un coût de forme générale log-linéaire.
	\item \textbf{Evaluation rapide :} \\
	Le coût du calcul (degré $n$) vaut deux fois le coût du calcul sur les fils de la racine de l'arbre (de tailles respectives $n/2$), plus un côut dû aux divisions, en utilisant à nouveau le même théorème, et sachant qu'ici aussi $a = b = 2$, on aura à nouveau un coût de forme générale log-linéaire. 
	\item \textbf{Somme de fractions :}\\
	Le calcul ressemble aux deux précédents, on utilise une nouvelle fois le théorème de calcul de complexité des algorithmes de stratégie \og diviser pour régner \fg. 
	Ici, on segmente à nouveau l'ensemble des calculs en deux parties, le coût total vaut deux fois le coût du calcul des deux \og sous-sommes \fg, plus l'addition de celles-ci, on a encore une fois $a = b = 2$, on en déduit une complexité de forme générale log-linéaire.
	\item \textbf{Interpolation rapide :}\\
	Au final, on aura une complexité similaire (somme des algorithmes précédents), mais:
	comme indiqué dans l'énoncé, on suppose que la multiplication de deux polynômes univariés à coefficients rationnels de degré borné par \textit{d} se fait en M($d \log{(d)} \log{\log{(d)}}$).
	On aura donc une complexité finale en $O(d ({\log{(d)}})^2 \log{\log{(d)}})$.
\end{enumerate}
\end{document}